Parallel linear congruential generators with prime moduli
Identifieur interne : 000246 ( Main/Exploration ); précédent : 000245; suivant : 000247Parallel linear congruential generators with prime moduli
Auteurs : Michael Mascagni [États-Unis]Source :
- Parallel Computing [ 0167-8191 ] ; 1998.
English descriptors
- Teeft :
- Absolute value, Algorithm, Binary, Binary tree, Canonical technique, Carlo, Carlo methods, Comput, Computational cost, Congruential, Congruential generation package, Congruential generators, Efficient algorithm, Elsevier science, Enumeration, Explicit enumeration, Explicit parameterization, Exponential, Exponential sums, Factorization, Finite fields, Independent neutron paths, Initial conditions, Integer, Integer addition, Integers modulo, Interprocessor correlation, Iterative search, Large moduli, Largest value, Lcgs, Lcgs modulo, Linear congruential generators, Linear search, Mascagnir, Maximal period, Mersenne, Mersenne primes, Modular addition, Modular multiplication, Modular reduction, Modulo, Modulus, Modulus lcgs, Monte carlo, Monte carlo computations, Multiplier, Neutron, Node, Number theory, Parallel comput, Parallel lcgs, Parallel machines, Parallel process, Parallel processes, Parallel pseudorandom number generation, Parameterization, Particular computation, Positive residue modulo, Prime factors, Prime modulus, Prime modulus lcgs, Primitive element, Primitive element modulo, Primitive elements modulo, Primitive modulo, Pseudorandom, Pseudorandom number, Pseudorandom number generation, Pseudorandom number generator, Pseudorandom number generators, Pseudorandom numbers, Random number generators, Recursion, Residues modulo, Riemann hypothesis, Same mapping, Sequences modulo, Small example, Southern mississippi, Theoretical measure, Total number, Tree node numbers, Tree nodes, Trial division, Uniform distribution, Unique pseudorandom number streams.
Abstract
Abstract: Linear congruential generators (LCGs) remain the most popular method of pseudorandom number generation on digital computers. Ease of implementation has favored implementing LCGs with power-of-two moduli. However, prime modulus LCGs are superior in quality to power-of-two modulus LCGs, and the use of a Mersenne prime minimizes the computational cost of generation. When implemented for parallel computation, quality becomes an even more compelling issue. We use a full-period exponential sum as the measure of stream independence and present a method for producing provably independent streams of LCGs in parallel by utilizing an explicit parameterization of all of the primitive elements modulo a given prime. The minimization of this measure of independence further motivates an algorithm required in the explicit parameterization. We describe and analyze this algorithm and describe its use in a parallel LCG package.
Url:
DOI: 10.1016/S0167-8191(98)00010-6
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000101
- to stream Istex, to step Curation: 000100
- to stream Istex, to step Checkpoint: 000234
- to stream Main, to step Merge: 000247
- to stream Main, to step Curation: 000246
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Parallel linear congruential generators with prime moduli</title><author><name sortKey="Mascagni, Michael" sort="Mascagni, Michael" uniqKey="Mascagni M" first="Michael" last="Mascagni">Michael Mascagni</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:9DC3B16F8C0AB13EF940DA91CCBFCB5432A91784</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1016/S0167-8191(98)00010-6</idno><idno type="url">https://api.istex.fr/document/9DC3B16F8C0AB13EF940DA91CCBFCB5432A91784/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000101</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000101</idno><idno type="wicri:Area/Istex/Curation">000100</idno><idno type="wicri:Area/Istex/Checkpoint">000234</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000234</idno><idno type="wicri:doubleKey">0167-8191:1998:Mascagni M:parallel:linear:congruential</idno><idno type="wicri:Area/Main/Merge">000247</idno><idno type="wicri:Area/Main/Curation">000246</idno><idno type="wicri:Area/Main/Exploration">000246</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Parallel linear congruential generators with prime moduli</title><author><name sortKey="Mascagni, Michael" sort="Mascagni, Michael" uniqKey="Mascagni M" first="Michael" last="Mascagni">Michael Mascagni</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Program in Scientific Computing and Department of Mathematics, The University of Southern Mississippi, Southern Station Box 10057, Hattiesburg, MI 39406-0057</wicri:regionArea><placeName><region type="state">Michigan</region></placeName></affiliation></author></analytic><monogr></monogr><series><title level="j">Parallel Computing</title><title level="j" type="abbrev">PARCO</title><idno type="ISSN">0167-8191</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1998">1998</date><biblScope unit="volume">24</biblScope><biblScope unit="issue">5–6</biblScope><biblScope unit="page" from="923">923</biblScope><biblScope unit="page" to="936">936</biblScope></imprint><idno type="ISSN">0167-8191</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0167-8191</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Absolute value</term><term>Algorithm</term><term>Binary</term><term>Binary tree</term><term>Canonical technique</term><term>Carlo</term><term>Carlo methods</term><term>Comput</term><term>Computational cost</term><term>Congruential</term><term>Congruential generation package</term><term>Congruential generators</term><term>Efficient algorithm</term><term>Elsevier science</term><term>Enumeration</term><term>Explicit enumeration</term><term>Explicit parameterization</term><term>Exponential</term><term>Exponential sums</term><term>Factorization</term><term>Finite fields</term><term>Independent neutron paths</term><term>Initial conditions</term><term>Integer</term><term>Integer addition</term><term>Integers modulo</term><term>Interprocessor correlation</term><term>Iterative search</term><term>Large moduli</term><term>Largest value</term><term>Lcgs</term><term>Lcgs modulo</term><term>Linear congruential generators</term><term>Linear search</term><term>Mascagnir</term><term>Maximal period</term><term>Mersenne</term><term>Mersenne primes</term><term>Modular addition</term><term>Modular multiplication</term><term>Modular reduction</term><term>Modulo</term><term>Modulus</term><term>Modulus lcgs</term><term>Monte carlo</term><term>Monte carlo computations</term><term>Multiplier</term><term>Neutron</term><term>Node</term><term>Number theory</term><term>Parallel comput</term><term>Parallel lcgs</term><term>Parallel machines</term><term>Parallel process</term><term>Parallel processes</term><term>Parallel pseudorandom number generation</term><term>Parameterization</term><term>Particular computation</term><term>Positive residue modulo</term><term>Prime factors</term><term>Prime modulus</term><term>Prime modulus lcgs</term><term>Primitive element</term><term>Primitive element modulo</term><term>Primitive elements modulo</term><term>Primitive modulo</term><term>Pseudorandom</term><term>Pseudorandom number</term><term>Pseudorandom number generation</term><term>Pseudorandom number generator</term><term>Pseudorandom number generators</term><term>Pseudorandom numbers</term><term>Random number generators</term><term>Recursion</term><term>Residues modulo</term><term>Riemann hypothesis</term><term>Same mapping</term><term>Sequences modulo</term><term>Small example</term><term>Southern mississippi</term><term>Theoretical measure</term><term>Total number</term><term>Tree node numbers</term><term>Tree nodes</term><term>Trial division</term><term>Uniform distribution</term><term>Unique pseudorandom number streams</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Linear congruential generators (LCGs) remain the most popular method of pseudorandom number generation on digital computers. Ease of implementation has favored implementing LCGs with power-of-two moduli. However, prime modulus LCGs are superior in quality to power-of-two modulus LCGs, and the use of a Mersenne prime minimizes the computational cost of generation. When implemented for parallel computation, quality becomes an even more compelling issue. We use a full-period exponential sum as the measure of stream independence and present a method for producing provably independent streams of LCGs in parallel by utilizing an explicit parameterization of all of the primitive elements modulo a given prime. The minimization of this measure of independence further motivates an algorithm required in the explicit parameterization. We describe and analyze this algorithm and describe its use in a parallel LCG package.</div></front></TEI><affiliations><list><country><li>États-Unis</li></country><region><li>Michigan</li></region></list><tree><country name="États-Unis"><region name="Michigan"><name sortKey="Mascagni, Michael" sort="Mascagni, Michael" uniqKey="Mascagni M" first="Michael" last="Mascagni">Michael Mascagni</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Mathematiques/explor/SophieGermainV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000246 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000246 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Mathematiques
|area= SophieGermainV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:9DC3B16F8C0AB13EF940DA91CCBFCB5432A91784
|texte= Parallel linear congruential generators with prime moduli
}}
| This area was generated with Dilib version V0.6.33. |  |